package cn.edu.xjtu.work.maxProfit;

/**
 * 122.买卖股票的最佳时机 II
 * <p>
 * 给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

public class SolutionI {
    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices));
    }

    /**
     * 动态规划算法 一天结束后要么持股票要么不持
     * <p>
     * 不持股票的话有两种情况,一种是前一天没有并且当天没买,另一种是前一天有但是当天卖了
     * <p>
     * 持股票的话也是两种情况,一种是前一天没有,但是今天卖了;另一种是前一天有今天也没卖
     * <p>
     * 因此只需要计算每种情况下二者的最大值即可
     *
     * @param prices 价格数组
     * @return 最大利润
     */
    public static int maxProfit(int[] prices) {
        if (prices.length == 0 || prices.length == 1) {
            return 0;
        }
        int len = prices.length;
        int hold = -prices[0];
        int noHold = 0;
        for (int i = 1; i < len; i++) {
            hold = Math.max(hold, noHold - prices[i]);
            noHold = Math.max(noHold, hold + prices[i]);
        }
        // 最后一天肯定是卖出利润最高
        return noHold;
    }

    /**
     * 动态规划,dp数组
     *
     * @param prices
     * @return
     */
    public static int maxProfit1(int[] prices) {
        if (prices.length == 0 || prices.length == 1) {
            return 0;
        }
        int[] hold = new int[prices.length];
        int[] noHold = new int[prices.length];
        hold[0] = -prices[0];
        noHold[0] = 0;
        for (int i = 1; i < hold.length; i++) {
            hold[i] = Math.max(hold[i - 1], noHold[i - 1] - prices[i]);
            noHold[i] = Math.max(noHold[i - 1], hold[i - 1] + prices[i]);
        }
        return noHold[noHold.length - 1];
    }

}
